package com.clstu.leetcode;

import java.util.HashMap;

/**
 * 208题前缀树
 */
public class Trie {
    public static void main(String[] args){
        String word = "hello";
        String prefix = "hel";
         Trie obj = new Trie();
         obj.insert(word);
        System.out.println("=========");
        System.out.println(obj.startsWith("hell"));
        System.out.println(obj.startsWith("hello"));
        System.out.println(obj.search("hello"));
    }

    public TridNode root = null;
    public Trie() {
        root = new TridNode();
    }

    public void insert(String word) {
        char[] chars = word.toCharArray();
        //遍历字符串添加到前缀树
        TridNode cur = root;
        for (char c : chars) {
            //如果下一跳不存在就创建
            int index = c-'a';
//            System.out.println(cur.nexts+"  "+index);
//            System.out.println(cur.nextMap);
            if(!cur.nextMap.containsKey(c)){
                TridNode tridNode = new TridNode();
                tridNode.pass = 1;
                cur.nextMap.put(c,tridNode);
            }
            TridNode next = cur.nextMap.get(c);
            //修改相应变量
            cur.pass++;
            cur = next;
        }
        //到最后end++;
        cur.pass++;
        cur.end++;
    }

    public boolean search(String word) {
        //依次遍历,如果结尾处的end>=1,则表明存在
        char[] chars = word.toCharArray();
        TridNode cur = root;
        for (char c : chars) {
            int index = c-'a';
            TridNode next = cur.nextMap.get(c);
            //如果查询不完
            if(next == null) return false;
            //后移
            cur = next;
        }
        //检查是否存在end
        return cur.end >0 ;
    }

    public boolean startsWith(String prefix) {
        //依次遍历,如果能够遍历完,则说明存在
        char[] chars = prefix.toCharArray();
        TridNode cur = root;
        for(int i=0;i<chars.length;i++){
            TridNode next = cur.nextMap.get(chars[i]);
            //如果不能遍历完
//            System.out.println("here");
            if(next == null) return false;
            //后移
            cur = next;
        }
        //如果遍历完了,一定是有前缀的
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

/**
 前缀树节点
 */
class TridNode {
    public int pass;
    public int end;
    public HashMap<Character,TridNode> nextMap = null;
    public TridNode(){
        nextMap = new HashMap<>();
    }
}